package com.husk.leetcode.dp;

import java.util.Arrays;

/**
 * <p>
 * 你有三种硬币，分别面值2元，5元和7元，每种硬币都有足够多
 * 买一本书27元
 * 如何用最少1硬币组合整好付清，不需要对方找钱
 * </p>
 *
 * @author hushunke@sm.vvip-u.com
 * @since 2021/3/30
 */
public class CoinChange {

    /**
     * 所需最少硬币数:
     * f(27) = min{f(27-2), f(27-5), f(27-7)} + 1
     * <p>
     * 拼不出来政正无穷
     * <p>
     * dp[x] = min{dp[x-2], dp[x-5], dp[x-7]} + 1
     * <p>
     * f(1) = Integer.MAX
     * f(0) = 0
     */


    /**
     * 322. 零钱兑换
     * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
     * 你可以认为每种硬币的数量是无限的。
     * <p>
     * https://leetcode-cn.com/problems/coin-change/
     * <p>
     * dp[amount] = min{dp[amount-coins[i]]} + 1, 0<=i<coin.length
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i - coins[j] >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    /**
     * 518. 零钱兑换 II
     * 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
     * <p>
     * https://leetcode-cn.com/problems/coin-change-2/
     * <p>
     * dp[amount] = sum(dp[x-coins[i]]), coins[i]<=x<=amount, 0<=i<coins.length
     *
     * @param amount
     * @param coins
     * @return
     */
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1;

        for (int i = 0; i < coins.length; i++) {
            for (int x = coins[i]; x <= amount; x++) {
                dp[x] += dp[x - coins[i]];
            }
        }
        return dp[amount];
    }

}
